#ifndef BASIC_STRING_HPP
#define BASIC_STRING_HPP

/**
 * @brief  basic_string  String 模板类
 *
 * 模仿标准库实现 string 模板类 支持 basic_string<char>   basic_string<wchar_t>
 */

#include "allocator.hpp"
#include "array.hpp"
#include "exceptdef.h"
#include <ostream> // import ostream

namespace TingSTL {
template <typename Char_Type, typename Alloc = allocator<Char_Type>>
class basic_string {
public:
    using allocator_type = typename Alloc;

    using value_type = typename allocator_type::value_type;
    using pointer = typename allocator_type::pointer;
    using const_pointer = typename allocator_type::const_pointer;
    using reference = typename allocator_type::reference;
    using const_reference = typename allocator_type::const_reference;

    using difference_type = typename allocator_type::difference_type;
    using size_type = typename allocator_type::size_type;

    // 先使用指针 简单代替 迭代器
    using iterator = value_type *;
    using const_iterator = const value_type *;
    // todo: 反向迭代器

    // 字符串 末尾标志位
    static constexpr Char_Type npos = static_cast<Char_Type>(0);
    // 初始 string 容器大小
    static constexpr size_type initBufferSize = 32;

private:
    iterator _buffer; // 储存字符串的起始位置
    size_type _size;  // 大小
    size_type _cap;   // 容量

public:
    // ////////////////// 构造 拷贝 移动 复制 析构  //////////////////
    basic_string() noexcept {
        this->tryInit();
    }

    ~basic_string() noexcept {
        allocator_type::deallocate(this->_buffer, this->_cap);
        this->_buffer = nullptr;
    }

    explicit basic_string(const value_type *str) :
        _cap(0), _size(0), _buffer(nullptr) {
        this->initFromCStr(str);
    }

    basic_string(const value_type *str, size_type n) :
        _cap(0), _size(0), _buffer(nullptr) {
        this->initFromCStr(str, n);
    }

    // 使用 swap&copy原则 实现 拷贝构造 移动构造 拷贝复制  移动复制
    basic_string(basic_string &other) {
        // TING_DEBUG("copy-deconstruction");
        if (other._size == 0) {
            tryInit();
            return;
        }
        this->_buffer = allocator_type::allocate(other._cap);
        this->_cap = other._cap;
        this->_size = other._size;
        copy(this->_buffer, other._buffer, other._size);
    }

    basic_string(basic_string &&other) :
        _cap(0), _size(0), _buffer(nullptr) {
        // TING_DEBUG("move-deconstruction");
        swap(other);
    }

    basic_string &
    operator=(basic_string other) // 当传入 左值 进行一次copy,
                                  // 传入右值的时候，进行一次 移动构造
    {
        swap(other);
        return *this;
    }

    basic_string &operator=(const value_type *str) {
        if (this->_buffer == nullptr) {
            initFromCStr(str);
        } else {
            if (str == nullptr) {
                this->_size = 0;
                return *this;
            }
            auto len = length(str);
            if (len >= _cap) {
                auto newCap = len + 1;
                auto newBuf = allocator_type::allocate(newCap);
                allocator_type::deallocate(_buffer, this->_cap);
                this->_cap = newCap;
                this->_buffer = newBuf;
            }
            copy(this->_buffer, str, len);
            this->_size = len;
        }
        return *this;
    }
    // ////////////////// 容量相关  //////////////////
    inline size_type len() const noexcept {
        return _size;
    }

    inline size_type size() const noexcept {
        return _size;
    }

    inline size_t capacity() const noexcept {
        return _cap;
    }

    inline void clear() const noexcept {
        this->_size = 0;
    }

    // ////////////////// 常用算法  //////////////////

    // 追加字符串
    basic_string &append(const value_type *str) {
        if (str == nullptr)
            return *this;

        auto len = length(str);
        if (len + this->_size >= this->_cap) {
            this->reallocate(len);
        }
        copy(this->_buffer + this->_size, str, len);
        this->_size += len;
        return *this;
    }

    basic_string &append(const basic_string &other) {
        if (other._size == 0)
            return *this;

        if (other._size + this->_size >= this->_cap)
            this->reallocate(other._size);
        copy(this->_buffer + this->_size, other._buffer, other._size);
        this->_size += other._size;
    }

    basic_string &operator+(const value_type *str) {
        return this->append(str);
    }

    basic_string &operator+(const basic_string &other) {
        return this->append(other);
    }

    // 对比字符串
    bool operator==(const basic_string &other) const {
        if (this->_size != other._size)
            return false;
        if (this->_size == 0)
            return true;
        return compare(other._buffer, this->_buffer, this->_size) == 0;
    }

    bool operator==(const value_type *str) const {
        auto len = length(str);
        if (len != this->_size)
            return false;
        if (this->_size == 0)
            return true;
        return compare(_buffer, str, len) == 0;
    }

    basic_string sub(size_type begin, size_type n) const {
        if (begin >= _size)
            return basic_string();
        n = std::min(_size - begin, n);
        return basic_string(this->_buffer + begin, n);
    }

    int find(const value_type *str, size_type begin = 0) const {
        auto len = length(str);
        return find(str, begin, len);
    }

    int find(const basic_string &other, size_type begin = 0) const {
        return find(other._buffer, begin, other._size);
    }

    array<basic_string> split(const value_type *str) const {
        int len = (int)length(str);
        if (len == 0 || _size == 0)
            return {};

        auto ret = array<basic_string>();

        int right = find(str, 0);
        int left = 0;

        while (left < _size) {
            if (left != right) {
                int subLen = (int)(right == -1 ? _size - left : right - left);
                ret.emplace_back(_buffer + left, subLen);
                left = left + subLen + len;
            } else {
                left += len;
            }
            right = find(str, left, len);
        }

        return ret;
    }

    // ////////////////// 迭代器相关  //////////////////
    inline const_iterator cbegin() const noexcept {
        return this->_buffer;
    }

    inline const_iterator cend() const noexcept {
        return this->_buffer + this->_size;
    }

    inline iterator begin() const noexcept {
        return this->_buffer;
    }

    inline iterator end() const noexcept {
        return this->_buffer + this->_size;
    }

    inline iterator begin() noexcept {
        return this->_buffer;
    }

    inline iterator end() noexcept {
        return this->_buffer + this->_size;
    }
    // ////////////////// misc  //////////////////

    // 转换为cStr
    inline const value_type *c_str() const {
        if (this->_buffer != nullptr)
            this->_buffer[_size] = npos; // 分配内存的时候就保证 cap > size
        return this->_buffer;
    }

    // 输出
    friend std::ostream &operator<<(std::ostream &os,
                                    const basic_string &str) {
        for (auto i = 0; i < str._size; ++i)
            os << *(str._buffer + i);
        return os;
    }

    // 交换两个 string 内容
    void swap(basic_string &rhs) noexcept {
        std::swap(this->_buffer, rhs._buffer);
        std::swap(this->_size, rhs._size);
        std::swap(this->_cap, rhs._cap);
    }

private:
    // //////////////////  算法相关 //////////////////////
    // 获取 字符长度
    static size_type length(const value_type *s) {
        if (s == nullptr)
            return 0;
        size_type len = 0;
        for (; *s != npos; ++s) {
            ++len;
        }
        return len;
    }

    // 比较字符串 在n范围内是否 相等
    static int compare(const value_type *lhs, const value_type *rhs,
                       size_type n) {
        int ret = 0;
        for (; n != 0; --n, ++lhs, ++rhs) {
            ret = *lhs - *rhs;
            if (ret != 0)
                return ret;
        }
        return 0;
    }

    static int findByChar(const value_type *str, size_type n, value_type c) {
        for (int pos = 0; pos != n; ++pos) {
            if (str[pos] == c)
                return pos;
        }
        return -1;
    }

    // 调用合适的算法 find
    int find(const value_type *patt, size_type begin,
             size_type pattLen) const {
        if (_size == 0 && pattLen == 0)
            return 0;
        if (begin > _size || pattLen == 0 || _size - begin < pattLen)
            return -1;
        const value_type *strBegin = this->_buffer + begin;
        size_type strLen = _size - begin;
        if (strLen < pattLen) {
            return -1;
        }
        if (strLen == pattLen) {
            return (int)(compare(strBegin, patt, pattLen) == 0 ? begin : -1);
        }
        if (pattLen == 1) {
            auto pos = findByChar(strBegin, strLen, patt[0]);
            return (int)(pos == -1 ? pos : begin + pos);
        }

        auto pos = kmpFind(strBegin, strLen, patt, pattLen);
        return (int)(pos == -1 ? pos : begin + pos);
    }

    // kmp 查找字符串
    static int kmpFind(const_pointer string, size_type stringLen,
                       const value_type *patt, size_type pattLen) {
        if (pattLen > stringLen || pattLen <= 1 || stringLen == 0)
            return -1;

        int *indexArr = new int[pattLen]{0};

        buildKmpIndexArray(indexArr, patt, pattLen);
        int s = 0;
        int p = 0;
        auto dLen = static_cast<int>(stringLen);
        while (s < dLen) {
            if (string[s] == patt[p]) // 匹配 后移
            {
                ++s;
                ++p;
                if (p == pattLen)
                    break;
            } else if (p > 0) { // 查表回滚
                p = indexArr[p - 1];
            } else { // 子串第一个字符都不匹配，无法回滚
                ++s;
            }
        }
        delete[] indexArr;
        if (p == pattLen)
            return s - p;

        return -1;
    }

    // kmp 算法 获取 index数组
    static void buildKmpIndexArray(int *indexArr, const value_type *str,
                                   size_type len) {
        if (len <= 1)
            return;
        size_type i = 1;
        int prefixLen = 0; // 当前前缀长度
        while (i < len) {
            if (str[i] == str[prefixLen]) // 前缀 字符 等于 后缀字符
            {
                ++prefixLen;
                indexArr[i] = prefixLen;
                ++i;
            } else {
                // 利用左子串 等与 右子串 的特点 ，直接找 左边前缀 后缀
                // 长度进行回滚
                if (prefixLen == 0) // 没有相同无法回滚
                {
                    indexArr[i] = 0;
                    ++i;
                } else { // 相同回滚
                    prefixLen = indexArr[prefixLen - 1];
                }
            }
        }
        // for(size_type i = 0;i<len;++i)
        // {
        //     TING_DEBUG("%zd,",indexArr[i]);
        // }
    }

    // //////////////////  内存管理 //////////////////////

    // 调整 容量大小 , 至少调整大小 1.5 倍率
    size_type reallocate(size_type needCap) {
        size_type newCap = std::max(needCap + _cap, _cap + (_cap >> 1));
        pointer newBuf = allocator_type::allocate(newCap);
        copy(newBuf, this->_buffer, this->_size);
        allocator_type::deallocate(this->_buffer, this->_cap);
        this->_cap = newCap;
        this->_buffer = newBuf;
        return this->_cap;
    }

    // 拷贝 拷贝src 到 dst， 长度限制 n
    static const_pointer copy(pointer dst, const_pointer src, size_type n) {
        size_type distance = std::abs(dst - src);
        TING_ASSERT(distance >= n,
                    "copy string error,distance is less n  (dst form "
                    "src )"); // 防止 同一个内存段相互拷贝 导致越界

        for (pointer temp = dst; n != 0; --n, ++temp, ++src) {
            *temp = *src;
        }
        return dst;
    }

    //  初始化相关
    void tryInit() noexcept {
        try {
            this->_buffer = allocator_type::allocate(initBufferSize);
            this->_cap = initBufferSize;
            this->_size = 0;
        } catch (...) // 分配内存失败
        {
            this->_buffer = nullptr;
            this->_cap = 0;
            this->_size = 0;
        }
    }

    void initFromCStr(const value_type *str, size_type n) {
        if (n == 0) {
            this->tryInit();
            return;
        }
        this->_cap = std::max(n + 1, initBufferSize);
        this->_size = n;
        this->_buffer = allocator_type::allocate(this->_cap);
        copy(this->_buffer, str, n);
    }

    void initFromCStr(const value_type *str) {
        if (str == nullptr) {
            this->tryInit();
            return;
        }
        auto len = length(str);
        this->initFromCStr(str, len);
    }
};
} // namespace TingSTL

// 重载 标准库 swap 实现
namespace std {
template <typename Char_Type, typename Alloc>
void swap(TingSTL::basic_string<Char_Type, Alloc> &lhs,
          TingSTL::basic_string<Char_Type, Alloc> &rhs) {
    lhs.swap(rhs);
}
} // namespace std

#endif